package cuppics;

import java.util.ArrayList;
import java.util.HashMap;
import java.util.List;
import java.util.Map;
import java.util.Map.Entry;

import org.junit.Test;

public class Prj5 {

	/**
	 * 2520 is the smallest number that can be divided by each of the numbers
	 * from 1 to 10 without any remainder.
	 * 
	 * What is the smallest positive number that is evenly divisible by all of
	 * the numbers from 1 to 20?
	 */
	@Test
	public void test() {

		Map<Long, Integer> primeMap = new HashMap<Long, Integer>();
		IntegerDivisor div = new IntegerDivisor();
		
		int upLimit = 20;
		for (int i = 2; i <= upLimit; i++) {
			
			div.divisor(i);
			merger2HighPrimeOrder( primeMap, div.primeMap);
			div.clear();
		}
		
		Long val = 1L;
		for( Entry<Long, Integer> entry : primeMap.entrySet()){
			val = (long) (val * Math.pow( entry.getKey(), entry.getValue()));
		}
		System.out.println("val =" + val);
	}

	private void merger2HighPrimeOrder(Map<Long, Integer> primeMap,
			Map<Long, Integer> primeMapDiv) {
		for( Entry<Long, Integer> entry : primeMapDiv.entrySet()){
			
			if( !primeMap.containsKey(entry.getKey())){
				primeMap.put(entry.getKey(),  entry.getValue());
			}
			
			if(primeMap.get(entry.getKey()) < entry.getValue()){
				primeMap.put(entry.getKey(), entry.getValue());
			}
			
		}
	}

	public static class IntegerDivisor {

		public Map<Long, Integer> primeMap = new HashMap<Long, Integer>();
		public List<Long> primeList = new ArrayList<Long>();

		public void clear() {
			primeMap.clear();
			primeList.clear();
		}

		public void divisor(long num) {

			if (num <= 1)
				return;

			long prime = getPrime(
					num,
					primeList.size() == 0 ? 2
							: primeList.get(primeList.size() - 1));
			if (prime < 0) {
				primeMap.put(num, 1);
				primeList.add(num);
				return;
			} else {

				primeList.add(prime);
				int count = 0;
				do {

					count += 1;
					num = num / prime;
				} while (num % prime == 0);

				primeMap.put(prime, count);

				divisor(num);

			}

		}

		private long getPrime(long num, long start) {

			for (long i = start; i <= Math.sqrt(num); i++) {
				if (num % i == 0) {
					return i;
				}
			}
			return -1;
		}

		@Override
		public String toString() {

			StringBuilder sb = new StringBuilder();
			for (Entry<Long, Integer> entry : primeMap.entrySet()) {
				sb.append(entry.getKey().toString() + "="
						+ entry.getValue().toString() + "\n");
			}

			for (int i = 0; i < primeList.size(); i++) {
				sb.append(primeList.get(i) + "--->");
			}
			return sb.toString();
		}

		public Long getLargestPrime() {
			return primeList.get(primeList.size() - 1);
		}

	}

}
